//给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。 
// 设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小
//的直线返回，S[0]相同则选择S[1]值较小的直线返回。 
// 示例： 
// 输入： [[0,0],[1,1],[1,0],[2,0]]
//输出： [0,2]
//解释： 所求直线穿过的3个点的编号为[0,2,3]
// 
// 提示： 
// 
// 2 <= len(Points) <= 300 
// len(Points[i]) = 2 
// 
//
// Related Topics 几何 数组 哈希表 数学 👍 33 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-09-08 19:32:40
 * @description 面试题 16.14.最佳直线
 */
public class BestLineLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 BestLineLcci fun=new BestLineLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int[] bestLine(int[][] points) {
		int ansNum = 0;
		int[] result = new int[2];
		for (int i = 0; i < points.length; i++) {
			int x1 = points[i][0];
			int y1 = points[i][1];
			// 保存斜率相同的点
			Map<String, List<Integer>> map = new HashMap<>();
			for (int j = i + 1; j < points.length; j++) {
				int x2 = points[j][0];
				int y2 = points[j][1];

				// 使用分数表示斜率，避免浮点数精度问题
				String key;
				if (x2 == x1) {
					key = "inf_" + x1; // 垂直线，用x坐标标识
				} else {
					int dx = x2 - x1;
					int dy = y2 - y1;
					int gcd = gcd(dx, dy);
					dx /= gcd;
					dy /= gcd;
					// 统一斜率表示，确保 (a,b) 和 (-a,-b) 被视为相同
					if (dx < 0) {
						dx = -dx;
						dy = -dy;
					}
					key = dx + "_" + dy + "_" + (x1 * dy - y1 * dx); // 添加截距信息
				}

				map.computeIfAbsent(key, k -> new ArrayList<>()).add(j);
			}

			// 找到当前点最多的直线
			for (List<Integer> list : map.values()) {
				if (list.size() + 1 > ansNum) {
					ansNum = list.size() + 1;
					result[0] = i;
					result[1] = list.get(0);
				} else if (list.size() + 1 == ansNum) {
					// 如果点数相同，选择索引较小的点
					if (i < result[0] || (i == result[0] && list.get(0) < result[1])) {
						result[0] = i;
						result[1] = list.get(0);
					}
				}
			}
		}

		return result;
	}

	// 计算最大公约数
	private int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
